from cmath import inf
from math import isqrt


maxn = 10000
f = [0] + [inf] * maxn
for i in range (1, isqrt(maxn) + 1):
    for j in range(i * i, maxn + 1):
        f[j] = min(f[j], f[j - i*i] + 1)
class Solution:
    """
     方法： 使用动态规划求解完全平方数问题
            f[i]表示和为i的完全平方数的最少数量
            状态转移方程：f[j] = min(f[j], f[j - i*i] + 1)
            其中i是小于等于j平方根的正整数
     
     Args:
         n: int - 需要分解为完全平方数之和的正整数
     
     Returns:
         int: 和为n的完全平方数的最少数量
     
     Time: O(n * sqrt(n)) - 外层循环遍历到sqrt(n)，内层循环遍历到n
     
     Space: O(n) - 需要一个长度为n的数组存储动态规划状态
     """
    def numSquares(self, n: int) -> int:
        return f[n]
        
        